/**
 * 
 */
package backtrack;

import utils.CreateUtils;

/**
 * @author Michael
 *
 */
public class PrintAllValidBracketPairs {

	
	public static void printAllValidBracketPairs(int leftRem, int rightRem, StringBuilder sb) {
		if (leftRem == 0 && rightRem == 0) {
			System.out.printf("%s \n", sb.toString());
		}
		else {
			if (leftRem > 0) {
				printAllValidBracketPairs(leftRem - 1, rightRem, sb.append("("));
				sb.setLength(sb.length() - 1);
			}
			
			if (rightRem > leftRem) {
				printAllValidBracketPairs(leftRem, rightRem - 1, sb.append(")"));
				sb.setLength(sb.length() - 1);
			}
		}
	}
	
	
	public static void printAllValidBracketPairs2(int leftRem, int rightRem, StringBuilder sb) {
		if (leftRem == 0) {
			for (int i = rightRem; i > 0; --i) {
				sb.append(")");
			}
			System.out.printf("%s \n", sb.toString());
			sb.setLength(sb.length() - rightRem);
		}
		else {
			if (leftRem < rightRem) {
				printAllValidBracketPairs2(leftRem, rightRem - 1, sb.append(")"));
				sb.setLength(sb.length() - 1);
			}
			printAllValidBracketPairs2(leftRem - 1, rightRem, sb.append("("));
			sb.setLength(sb.length() - 1);
		}
	}
	/**
	 * 
	 */
	public PrintAllValidBracketPairs() {
		// TODO Auto-generated constructor stub
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		int n = CreateUtils.randNonNegInt(10);
		n = 3;
		//printAllValidBracketPairs(n, n, new StringBuilder());
		printAllValidBracketPairs2(n, n, new StringBuilder());
	}

}
